	package my.study.java.basic.algorithm.sorts;

import java.util.Random;

/**
 * 
 * 归并排序是利用分治法来对序列进行排序，首先，它不断地分割序列直到各子序列都成为单元素序列，
 * 然后，它不断成对儿的合并各个序列直至恢复整个序列，最后一次合并完成时，整个序列也就被排序了
 * 算法复杂度：O(NlgN)
 * 
 * @author fanhongjie
 * 
 */
public class MergeSort {
	private static final int N = 40;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Element array[] = new Element[N];
		Random random = new Random();
		for (int i = 0; i < N; i++) {
			array[i] = new Element(random.nextInt(2 * N));
		}
		System.out.print("Init:\t");
		for (int i = 0; i < N; i++) {
			System.out.print(array[i].getValue() + "\t");
		}
		System.out.println();
		MergeSort(array, 0, N - 1);
		System.out.print("Result:\t");
		for (int i = 0; i < N; i++) {
			System.out.print(array[i].getValue() + "\t");
		}

	}

	private static void MergeSort(final Element array[], final int start, final int end) {
		if (start == end) {
			return;
		} else if (start + 1 == end) {
			if (array[start].compareTo(array[end]) > 0) {
				Element elem = array[start];
				array[start] = array[end];
				array[end] = elem;
			}
			return;
		} else {
			int mid = (start + end) / 2;
			MergeSort(array, start, mid);
			MergeSort(array, mid + 1, end);
			Merge(array, start, mid, end);
		}
	}

	private static void Merge(Element array[], int start, final int mid, final int end) {
		int start1 = start;
		int start2 = mid + 1;
		Element[] newArray = new Element[end - start + 1];
		int newIndex = 0;
		while (start1 <= mid && start2 <= end) {
			if (array[start1].compareTo(array[start2]) > 0)
				newArray[newIndex++] = array[start2++];
			else
				newArray[newIndex++] = array[start1++];
		}
		while (start1 > mid && start2 <= end) {
			newArray[newIndex++] = array[start2++];
		}
		while (start2 > end && start1 <= mid) {
			newArray[newIndex++] = array[start1++];
		}
		for (int i = start; i <= end; i++) {
			array[i] = newArray[i - start];
		}
	}

}
